#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef struct{
	long long a[4][4];
}AD;
AD emt,one,a;
long long AtyPe[4][4] = {{1,1,0,1},{1,2,1,1},{0,0,1,0},{0,0,0,1}};
AD tms(AD a,AD b)
{
	AD res = emt;
	for(int i = 0;i < 4;i++)
	{
		for(int j = 0;j < 4;j++)
		{
			for(int k = 0;k < 4;k++)
			{
				res.a[i][j] += a.a[k][j] * b.a[i][k];
				res.a[i][j] %= mod;
			}
		}
	}
	return res;
}
AD qmi(AD a,long long b)
{
	AD res = one;
	while(b)
	{
		if(b & 1)
		{
			res = tms(res,a);
		}
		a = tms(a,a);
		b >>= 1;
	}
	return res;
}
int n,T,m;
vector<char> s[31];
char t[100011];
int kmp[100011],mx[1000011];
inline void BF()
{
	int ans = 0;
	for(int i = 1;i < s[n].size();i++)
	{
		int j = mx[i - 1];
		if(j == m) j = kmp[m];
		while(t[j + 1] != s[n][i] && j) j = kmp[j];
		if(t[j + 1] == s[n][i]) mx[i] = j + 1;
		else mx[i] = 0;
		if(mx[i] == m) ans++;
	}
	cout << ans << "\n";
}
signed main()
{
for(int i = 0;i < 4;i++) for(int j = 0;j < 4;j++) one.a[i][j] = AtyPe[i][j];
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	freopen("brotherhood.in","r",stdin);
	freopen("brotherhood.out","w",stdout);
	s[1].push_back('#'),s[1].push_back('0');
	s[2].push_back('#'),s[2].push_back('1');
	for(int i = 3;i <= 30;i++)
	{
		s[i].push_back('#');
		for(auto c:s[i - 1]) if(c != '#') s[i].push_back(c);
		for(auto c:s[i - 2]) if(c != '#') s[i].push_back(c);
	}
	cin >> n >> T;
	while(T--)
	{
		cin >> (t + 1);
		m = strlen(t + 1);
		for(int i = 2;i <= m;i++)
		{
			int j = kmp[i - 1];
			while(t[j + 1] != t[i] && j) j = kmp[j];
			if(t[j + 1] == t[i]) kmp[i] = j + 1;
			else kmp[i] = 0;
		}
		int fs;
		for(fs = 1;s[fs].size() - 1 < m;fs++);
		if(n <= fs + 4)
		{
			BF();
			continue;
		}
		int lens = s[fs].size() - 1,lent = s[fs + 1].size() - 1;
		a = emt;
		fs += 4;
		for(int i = 1;i < s[fs].size();i++)
		{
			int j = mx[i - 1];
			if(j == m) j = kmp[m];
			while(t[j + 1] != s[fs][i] && j) j = kmp[j];
			if(t[j + 1] == s[fs][i]) mx[i] = j + 1;
			else mx[i] = 0;
		}
		int len1 = lent + lens,len2 = lent + lens + lent;
		for(int i = m;i <= len2;i++)
		{
			if(mx[i] == m)
			{
				if(i <= len1)
				{
					a.a[0][0]++;
				}
				a.a[1][0]++;
			}
		}
		for(int i = len1 + 1;i < len1 + m;i++) if(mx[i] == m) a.a[2][0]++;
		for(int i = len2 + 1;i < len2 + m;i++) if(mx[i] == m) a.a[3][0]++;
		fs -= 2;
		a = tms(a,qmi(one,(n - fs >> 1) - 1));
		if((n - fs) & 1)
		{
			cout << a.a[1][0] << "\n";
		}else{
			cout << a.a[0][0] << "\n";
		}
	}
	return 0;
}
